﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using ProjectEuler.Linq;

namespace ProjectEuler.Problems
{
    using Triple = Tuple<Int32, Int32, Int32>;

    [EulerProblem(9, 31875000)]
    [Description("Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.")]
    internal sealed class Problem009 : EulerProblem
    {
        public override Object Solve()
        {
            return PrimitivePythagoreanTriples(1000 / 2).Single().Product();
        }

        private static IEnumerable<Triple> PrimitivePythagoreanTriples(Int32 sumhalf)
        {
            // http://en.wikipedia.org/wiki/Pythagorean_triple#Generating_a_triple

            return from m in (1).To((Int32)(sumhalf.SquareRoot()))
                   from n in (1).To(m - 1)

                   where m * (m + n) == sumhalf

                   let m2 = m.Square()
                   let n2 = n.Square()

                   let a = 2 * m * n
                   let b = m2 - n2
                   let c = m2 + n2

                   select new Triple(a, b, c);
        }
    }
}
